//给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）
//。 
//
// 
//
// 示例 1： 
//
// 
//输入：left = 5, right = 7
//输出：4
// 
//
// 示例 2： 
//
// 
//输入：left = 0, right = 0
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：left = 1, right = 2147483647
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= left <= right <= 2³¹ - 1 
// 
//
// Related Topics 位运算 👍 539 👎 0


package LeetCode.editor.cn;


import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @author ldltd
 * @date 2024-12-16 11:23:56
 * @description 201.数字范围按位与
 
 */
 
public class BitwiseAndOfNumbersRange {
    public static void main(String[] args) {
    //测试代码
    BitwiseAndOfNumbersRange fun = new BitwiseAndOfNumbersRange();
    Solution solution= fun.new Solution();
        System.out.println(9&10&11%12);
        //101 110 111
        System.out.println(solution.rangeBitwiseAnd(5,7));
        List<Integer> aa=new ArrayList<>();
        List<Integer> aza=new ArrayList<>();
        List<Integer> collect = aa.stream().collect(Collectors.toList());
        aza.addAll(collect);
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //超时
    public int rangeBitwiseAnd1(int left, int right) {
        return IntStream.range(left, right).parallel()
                .reduce((a, b) -> a & b)
                .orElse(0);
    }
    //没差，一样超时
    public int rangeBitwiseAnd2(int left, int right) {
        int res=left;
        for (int i = left+1; i <=right; i++) {
            res&=i;
        }
        return res;
    }
    //还是超时
    public int rangeBitwiseAnd3(int left, int right) {
        int res=0;
        for (int i = 0; i < 32; i++) {
            int t=0;
            for (int j = left; j <=right; j++) {
                t+=(j>>(i)&1);
            }
            if(t%2!=0){
                res|=(1<<i);
            }
        }
        return res;
    }
    //&了以后，只要有一个1，那0,那么就是0，所以只需要找出
    public int rangeBitwiseAnd4(int left, int right) {
        int m=left;
        int res=0;
        int k=0;
        while (m!=0){
            int t=0;
            for (int j = left; j <=right; j++) {
                t+=(j>>(k)&1);
            }
            if(t%2!=0){
                res|=(1<<k);
            }
            m>>=1;
            k++;
        }
        return res;
    }
    public  int rangeBitwiseAnd5(int left, int right) {
        int shift = 0;
        // 找到公共前缀
        /*
        * 1000
        * 0111
        * 0110
        * 如果没有对齐，那么就都是0
        *
        *
        * 1100
        * 1101
        * 1110
        * 1111
        * 如果对齐了，其实只需要关注最大和最小的前缀
        *
        * */
        while (left < right) {
            left >>= 1;
            right >>= 1;
            ++shift;
        }
        return left << shift;
    }


    /*
    * //Brian Kernighan 算法
    * n&(n-1)
    * 会把n最右边的1抹掉
    * 比如12
    * 1100 12 n
    * 1011 11 n-1
    * 1000  8 n&(n-1)
    * */
    public int rangeBitwiseAnd(int m, int n) {
        while (m < n) {
            // 抹去最右边的 1,直到m == n
            n = n & (n - 1);
        }
        return n;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
